Corelab Seminar
2018-2019
Eleni Bakali
Markov chains and phase transitions for TotP-complete problems
Abstract.
We consider weighted versions of TotP-complete problems. We study the complexity of computing these weighted sums and show the existence of phase transition from NP-hard to approximate to approximable with FPRAS. We also study Markov chains for these problems and show the existence of phase transitions from exponential to polynomial mixing time.